---

Prospective PhD students: Information about how to apply (to start in Autumn of 2027) will be here: https://www.ox.ac.uk/admissions/graduate/courses/dphil-computer-science. Prospective students should feel free to get in touch if any of the projects described here sound interesting, or if you have other related ideas in algorithms or complexity theory.

Research Interests

I work on the design and analysis of randomised algorithms. Randomised algorithms arise in many computational contexts including communication and information spread in networks, analysing computational models from statistical physics (and other models where local interactions influence global structure), and learning. My research focuses on the rigorous, mathematical analysis of these algorithms - proving results about how long the algorithms take, and how accurate they are. I am also interested in related questions from computational complexity where the goal is to figure out which computational problems can be solved with fast (randomised) algorithms and which problems provably can't be solved with fast algorithms. This research is part of the Algorithms and Complexity Theory research theme at Oxford.

Recent results, current projects, and potential PhD projects:

• Contention resolution.

  A contention resolution protocol is a simple randomised algorithm which is used by independent agents to access a shared resource. These algorithms give rise to difficult and interesting mathematical questions that apply in natural settings. In the basic model, agents arrive over time, according to a probability distribution, and have no way to communicate with each other except by attempting to access the resource. If two agents attempt access at the same time, they "collide" and must try again later. A backoff protocol is a simple randomised algorithm that agents use to determine when to attempt access and when to wait. The simplest example is binary exponential backoff where an agent that has already collided k times makes a random decision at each step, attempting access with probability 2^−k and waiting with probability 1-2^-k. Based on the model of Frank Kelly, David Aldous proved that binary exponential backoff is unstable for any positive rate of arrival, in the sense that the underlying random process is not positive recurrent. Informally, this says that the number of waiting agents builds up over time, even if the rate at which they arrive is arbitrarily low. Aldous conjectured in 1987 that the same is true for any backoff protocol. After lots of work, John Lapinskas and I finally proved this in 2026 (the paper is here). There are lots of interesting open problems, both in the original model of Kelly, and in other models where contention is mitigated by the presence of queues, as in this paper with Hesham Al-Ammal and Phil MacKenzie, or where arrivals are adversarial, as in this paper by Bender, Kopelowitz, Kuszmaul, and Pettie.



• Spin systems: sampling and approximate counting.

  One of the most important domains where randomised algorithms are studied is the area of spin systems. In a spin system, a configuration assigns a "spin" to every vertex of a graph. Spins interact locally along the edges of the graph, and these interactions give rise to a global distribution on configurations, called the Gibbs distribution. A famous example is the Ising model. Research in our area focuses on determining which model parameters give rise to fast algorithms for sampling configurations from the Gibbs distribution. Most of my research in this area is joint with Andreas Galanis and our joint students. Here is a paper with our jointly-supervised PhD student, Paulina Smolarova. This paper gives a fast algorithm in a setting where the underlying graph is random (so there are two levels of randomness). Sometimes, it is possible to give fast algorithms on random graphs in parameter regimes where it is conjectured that fast algorithms don't exist for worst-case graphs. There are plenty of open questions about identifying the boundary between where fast algorithms exist and where they don't. Andreas and I are interested in supervising more PhD students in this area (and related areas).

  Many important properties of a spin system can be determined by estimating a function called its "partition function". I won't give technical details here, but you can find a very gentle introduction to a related type of partition function (along with a reference to more of our research in this area) here . The research field that studies algorithms for estimating partition functions is called "computational counting". The study of counting complexity goes back to Les Valiant in the 1970s, but in the context of randomness and approximation there are additional challenges. Here is an early paper with Martin Dyer, Catherine Greenhill, and Mark Jerrum, which identifies a key complexity class for approximate counting, centred around a problem called #BIS, which is the problem of approximately counting the independent sets of a bipartite graph. By now there are many computational problems and classes of computational problems which are known to be equivalent to #BIS, but we still don't know whether it even has a fast approximation algorithm (with or without randomness), and this is a tantalising open problem. Here is a paper with Jerrum explaining the relationship between #BIS and spin systems.
  
  

• Analysing processes on networks.

  Some of my research involves the study of random processes on graphs. For example, the Moran process is a process which models the spread of genetic mutations in graphs. The goal is to derive rigorous probabilistic bounds on how these mutations spread over time (as a function of the graph). Some of my work in the area includes this paper (joint with Galanis, Andreas Goebel, Lapinskas, and Dave Richerby) and this paper (joint with Lapinskas and Richerby). There are lots of open problems. For example, not much is known when there are several types of mutation, and not much is known about convergence times on specific families of graphs. There are also other interesting related models. For example, the voter model, which models the spread of competing ideas in social networks. Here is a recent paper with Galanis and our jointly supervised PhD student Xandru Mifsud. analysing a random walk on an evolving random cluster configuration. The random cluster model is another model related to spin systems. Random walks on randomly evolving environments is a popular research area.

  
  
• Approximately counting graph homomorphisms and related structures

  A lot of progress in approximate counting (including randomised approximate counting) has come from understanding key graph structures such as graph homomorphisms. Often the key ideas come from the study of the structures themselves (which turn out to be complicated and fascinating!). Standa Zivny and I are interesting in jointly superivising a PhD in this area. Here is a joint paper with our previous jointly-supervised PhD student Jacob Focke (and with Marc Roth) which uses methods related to graph homomorphisms to obtain approximate-counting results relevant to databases. A recent paper with Roth (see here) uses this kind of analysis to deterermine the fine-grained complexity of counting subgraphs, modulo 2.

Links

• publications
• cv
• projects and PhD students